package 力扣;

/**
 * @author yyq
 * @create 2022-03-22 19:08
 */
public class leetcode28 {
    public static void main(String[] args) {
        int i = strStr("aabaaabaaac", "aabaaac");
        System.out.println(i);
    }
    public static int[] getNext(String s1){
        char[] chars = s1.toCharArray();
        int[] next=new int[s1.length()];
        //初始化 j从零开始 i从1开始
        // 其中 j 表示前缀的指针
        //     如果当前 两个指针指向的数值相同，则 j+1 表示next[i]
        // 其中 i 表示后缀的指针
        next[0] = 0;
        int j = 0;
        for (int i = 1; i < s1.length(); i++) {
            //情况一 如果两个指针指向的数值相同
            if(chars[j]==chars[i]){
                next[i] = j + 1;
                j++;
            }
            //情况二 如果两个指针指向的数值不同
            else {
                while(j!=0 && chars[j]!=chars[i]){
                    j=next[j-1];
                }
                if(j==0){
                    next[i]=0;
                    i++;
                }
            }

        }
        return next;
    }
    public static int strStr(String haystack, String needle) {
        if(needle.equals("")) return 0;
        char[] a = haystack.toCharArray();
        char[] b = needle.toCharArray();
        int[] next = getNext(needle);
        int j=0;
        int i=0;
        while(i<haystack.length()) {
                // 如果字符匹配
                if(b[j] == a[i]) {
                    j++;
                    i++;
                    if(j==needle.length()) return i-needle.length();
                    continue;
                }
                // 如果字符不匹配
                if(b[j] != a[i]) {
                    // 防止第一个字符不匹配无限循环
                    if(j==0) {
                        i++;
                        continue;
                    }
                    // 需要重新定位 j 指向的位置
                    j = next[j-1];
                }
        }
        return -1;
    }
}
